1. Field of the Invention
The present invention relates to a method and system for reliable transfer of data. In particular, the present invention provides a method and system of error correction coding to ensure that large, multimedia data files, including digitized music, still images or moving images, such as may be transmitted using one-way satellite broadcasting, are received error-free despite the effects of various types of noise interfering with the transmitted signal.
2. Description of Related Art
Today, the availability of powerful digital computational tools has yielded the ability to present information and data in forms that go far beyond text and numbers. There now exists the capability to create and share data in more complex multimedia forms, using graphics, audio, still images, moving images (video), and combinations thereof. However, digital multimedia data generally is far larger in size than text data. For example, whereas a conventional text file usually occupies less than 50 Kilobytes (Kbyte), just one minute of compressed video requires up to 10 Megabytes (Mbyte), almost 200 times larger in size.
The presentation of information in multimedia form therefore creates two problems--storage and communication. Storage has improved dramatically over the past few years. For example, personal computers (PCs) can now store inexpensively many Gigabytes (Gbyte) of data, and the cost-per-Gbyte is becoming less expensive every day.
Communications, however, remain a problem. Historically, the oldest method of distributing large amounts of information has been printed material, usually in the form of magazines and books. However, this method is relatively expensive, takes days to complete, is limited to presenting data in text, pictorial or graphic form, and is difficult to update or change. Distribution of information via audio cassette or video cassette, while less costly and allowing information to be presented in audio and video form, is still relatively slow in that shipment of the physical item containing the information must take place, and the cassette itself still makes it relatively difficult to update and change the information.
More practical than printed material and cassettes, graphics, music and other information may be digitized into computer data files, referred to as "large digital objects," which in turn may be transferred from a host computer to a potentially large number of subscriber computers. One common way of transferring data files is via a public or private computer network, in which the data files are transmitted by the host computer and received by the subscriber computers over phone lines via a modem. Although distribution via modems may work well for multi-Kbyte files, transmitting multi-Mbyte data files is impractical even when using the fastest modems, because the transmission speed of modems is constrained by the relatively low bandwidth of the telephone lines. For example, reliably retrieving just one large data object using the Internet, or other public or private networks, even when using ISDN lines, may take many minutes to many hours, and is relatively expensive.
To avoid overloading expensive private networks, many companies distribute large text files and other large digital objects using CD-ROM disks, each of which can hold, for example, up to 660 Mbytes of data. While the cost of distribution is moderate in comparison to using a network, the distribution of CD-ROM disks suffers from one major drawback shared by the oldest methods of information distribution--it can take one or more days, in comparison to the theoretically near-instantaneous communication potential that digital information should enjoy. Further, to update this CD-ROM based information, new CD-ROMS must be provided, usually from every three months to a year.
To overcome the problems associated with the above methods of distribution, distributors of large digital objects are turning to satellite broadcasting. Satellite broadcasting provides not only distribution over large geographical areas, for example, the entire United States and Canada, but potentially has the high bandwidth capacity required to transmit large digital objects at high speeds, thus reducing the transmission time to seconds. Moreover, the cost of satellite broadcasting, on a per-user basis, is comparatively less than the respective costs of the above methods. A one-way broadcast satellite system, shown in FIG. 1, transfers data from the host computer 1 to a satellite transmitter device 2. The satellite transmitter device 2 in turn transmits, through an uplink antenna 4, the data to a satellite 5 using modulation techniques well-known in the art. The satellite 5 retransmits the data to one or more downlink antennas 6 and satellite receiver devices 7. The satellite receiver device 7 transfers the data to the subscriber computer 8.
In such a system, it is essential in most applications that the transferred data files are reliably received in perfect condition at all the subscriber computers. For example, the transferred data file from the host may contain sensitive financial information in which no errors are acceptable. One notable drawback of one-way satellite broadcast systems, however, as compared to other standard methods of information distribution such as the above-described computer networks, is the inability of the subscriber computers to inform the host that a reception error has occurred.
Another drawback of satellite broadcasting is a greater vulnerability of the transmitted signal to various forms of noise interference present in the transmission channel.
One form of noise that is always present in the channel is "white" noise. For example, white noise is introduced in the satellite channel by the thermal radiation of the gaseous constituents of the earth's surface. The strength and frequency of this noise varies, and it sometimes overpowers the transmitted signal causing it to be received erroneously. Because of white noise, a transmitted binary "zero" bit is occasionally received erroneously as a binary "one" bit, and vice-versa. Such errors are known as bit errors. White noise generally tends to cause isolated bit errors in a transmitted message. Although these bit errors are usually spread out throughout the message, they can be easily detected and corrected, because they are isolated.
In contrast with white noise, "impulse" noise tends to wipe out long sequences of consecutive bits. Such errors are known as "burst" errors. Their duration varies from a few milliseconds to a few seconds, but certain phenomena, such as rainstorms or sunspots, can cause burst errors of even longer duration such as a few minutes. Unlike bit errors due to white noise, burst errors are not distributed over the entire message, but only a portion thereof. However, burst errors are more difficult to detect and correct, because they wipe out so many consecutive bits of data.
Well-known error detection and correction (EDAC) schemes are used to reduce the effects of errors caused by white noise. EDAC generally operates at the bit level by adding enough redundant data bits to the data to detect and correct the received data. In practice, EDAC can only detect and correct a limited amount of bit errors. The redundant data added to the original data, however, obviously increases the amount of data to be transmitted and thus the transmission bandwidth and transmission time. Well-known EDAC schemes include Hamming, Viterbi, Reed-Solomon, and other forward error correction (FEC) coding schemes.
Interleaving may also be performed at the bit level. Interleaving rearranges the data bits so that they are non-sequentially transmitted. The subscriber computer deinterleaves the received bits to reorder the bits as they originally appeared. This technique reduces the effect of errors in a sequence of bits. Although interleaving does not in itself correct those bit errors, by non-sequentially reordering the data bits in a block of data that is to be transmitted by the host computer, the bit errors are more uniformly distributed over the received block of data upon deinterleaving by the subscriber computer. By isolating the bit errors, interleaving enhances bit-level EDAC coding performance. Both EDAC and interleaving can also be performed on data symbols representing groups of bits, such as bytes.
In satellite broadcast systems, the transmitted data bits or symbols are most likely to be organized into large groups called packets, and a large digital object is transmitted as a sequence of packets. The addressed subscriber computers reconstruct the large digital object from the received packets. The above-described noise bursts, especially those due to rainstorms and sunspots, can typically damage one or more long sequences of consecutive packets, the effect of which is shown in FIG. 2. Those packets are either not received by one or more of the subscriber computers or are received severely corrupted. Although bit-level EDAC schemes might be able to correct some of the corrupted packets, depending on the number of erroneous bits in those corrupted packets, these schemes are simply not robust enough to correct the great majority of those corrupted packets. This is because, in extended periods of burst noise, a large amount of both the original data bits and redundant EDAC bits in a packet are received corrupted, thus making bit-level error correction, and thus packet-level error-correction, impossible. Moreover, EDAC schemes are useless in the case of those packets not received.
One known method for reducing the effect of burst errors in satellite broadcast systems is retransmission of those packets that were not received or were received corrupted and could not be corrected (hereinafter those packets are simply referred to as "lost"). For example, a host computer may broadcast via satellite to two geographically widely-separated subscriber computers A and B. Due to this wide separation, subscriber computer A and subscriber computer B may experience different weather conditions, and thus different patterns of noise. For example, subscriber computer A may lose 20% of the transmitted packets, while subscriber computer B may successfully receive all the transmitted packets.
Although it is possible to rebroadcast the entire file to all the subscriber computers, this method is costly, wastes time and bandwidth, and prevents the satellite channel from being used for other purposes. In the above example, subscriber computer A would identify the lost packets (by examining the serial numbers of the correctly received packets) and would ask the host computer to retransmit the packets it missed until the entire large digital object could be reconstructed perfectly by subscriber computer A. The request for missed packet retransmission is made through a back channel, and the host computer rebroadcasts those missed packets via satellite. Alternatively, the host computer retransmits those missed packets only to subscriber computer A through the back channel.
Retransmission of lost packets requires, however, (1) two-way communication back channels from all of the subscriber computers to the host computer so each subscriber computer can inform the host computer of which packets were lost, and (2) a retransmission protocol between the host computer and the subscriber computers. Each back channel usually takes the form of a modem and telephone lines, or is part of a standard computer network. The back channel therefore has a limited bandwidth and can timely transmit only a limited amount of information. Back channels are also expensive. Further, retransmission increases the time required to distribute the large digital object, and prevents the host computer and subscriber computers from doing other tasks.
Thus, none of the current error correction schemes or data retransmission techniques provides a reliable and efficient method of transferring large digital objects over a one-way broadcast satellite system.